package sword_offer;

/**
 * @ClassName _12ExitsPathInMatrix
 * @Description: TODO
 * @Author: yongliang.ma
 * @Create_time:2022/10/8 21:58
 */
public class _12ExitsPathInMatrix {

    public boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                boolean exist = backtrace(board, i, j, word, 0, visited);
                if (exist){
                    return true;
                }
            }
        }

        return false;
    }

    public boolean backtrace(char[][] board, int boardX, int boardY, String word, int wordIndex, boolean[][] visited){
        // 剪枝
        if (boardX < 0 || boardX == board.length || boardY < 0 || boardY == board[0].length || word.charAt(wordIndex) != board[boardX][boardY] || visited[boardX][boardY]){
            return false;
        }

        // 判断是否已经便利完Word字符串
        if (word.length() == wordIndex + 1)
            return true;

        // 改变当前字符访问状态，递归下一层，分别是上下左右探索
        visited[boardX][boardY] = true;
        boolean up = backtrace(board, boardX - 1, boardY, word, wordIndex + 1, visited);
        if (up)
            return true;// 拿到之后直接返回，避免后续的无必要的回溯过程
        boolean down = backtrace(board, boardX + 1, boardY, word, wordIndex + 1, visited);
        if (down)
            return true;
        boolean left = backtrace(board, boardX, boardY - 1, word, wordIndex + 1, visited);
        if (left)
            return true;
        boolean right = backtrace(board, boardX, boardY + 1, word, wordIndex + 1, visited);
        if (right)
            return true;
        // 状态复原
        visited[boardX][boardY] = false;

        return false;
    }
}
